Installations and imports
import networkx as nx
import matplotlib.pyplot as plt
import random
from typing import List
from dataclasses import dataclass
This part is about creating random graphs with different probabilites and analyzing the data about the maximum number of node connected together.
n = 100 # number of nodes
p = 0.1 # probability to connect with an other node
x = []
y = []
Gs = []
def generatGraph(p, ax):
G = nx.fast_gnp_random_graph(100,p)
Gs.append(G)
nx.draw_networkx(G, ax=ax, node_size=150, with_labels = False)
largest = len(sorted(nx.connected_components(G), key=len, reverse=True)[0])
ax.set_title("Probability : " + str(p) + "\nSize of the largest connected component " + str(largest))
ax.axis("off")
x.append(p)
y.append(largest)
fig, axs = plt.subplots(20,5,figsize=(35,140))
for i in range(100):
generatGraph(i/100, axs[i//5, i%5])
We generate graphs of a 100 nodes with a certain probability p of a node beeing connected to any other nodes.
We then use this function a 100 time and variate the probability between
0.01 and 1. We can see that it quickly form big groups of nodes that
are linked together.
We log the biggest group of node for each probability and trace the next graph :
plt.plot(x,y)
fig = plt.gcf()
fig.set_size_inches(10, 3)
fig.legend(["Number of Nodes connected together"])
plt.xlabel("Probability p")
plt.ylabel("Largest connected component")
We can observe that quickly, from p=0.05 (5%) or p=0.06 (6%), all the nodes are connected together.
def plot_degree_dist(G, ax, p):
degrees = [G.degree(n) for n in G.nodes()]
ax.set(xlim=(0, 100), ylim=(0, 40))
ax.hist(degrees, bins=20)
ax.set_title("Probability : " + str(p))
fig, axs = plt.subplots(10,10,figsize=(40,40))
i=0
for G in Gs:
plot_degree_dist(G, axs[i//10, i%10], i/100)
i += 1
We can observe thanks to the graphs that the average number of neighbors increase when the probability p increase too. We can see the blue shape moving from left to right when we increase the probability of each node to connect to others. So, when a node have few chances to connect himself, the average number of connections is low. At the end, when the probability is near to 1, the number of links for each node is near to the number of nodes.
@dataclass
class Node(object):
ID: int
Value: int
Timing: float
NodeConnected: int
Karma_tot: int
Karma_defect: int
def findNode(list, id):
for n in list:
if n.ID == id:
return n
Then we make a first version of the game that play witout interferences.
First we create 10 nodes, all with the value 0.
Then we make each node play.
We search the node with the biggest value and then connect the playing
node to it. If some nodes have the same maximum value, we select one
randomly.
def simple_game_without_interference():
G = nx.Graph()
Nodes = []
n = 100
# We create n nodes, each one has an id, a value initialized to 0 and a random timing value
# Then we add them to the graph
for i in range(n):
node = Node(i, 0, random.random(), -1 ,0, 0)
Nodes.append(node)
G.add_node(i, data = Node)
# We sort the nodes by the timing value to determine the order in which the nodes will play
Nodes = sorted(Nodes, key=lambda x: x.Timing)
print("First Node : ", Nodes[0])
# For each node
for nodePlaying in Nodes:
# We take the node by timing order
# We make a list of nodes to which the playing node can connect (every node except him)
index = Nodes.index(nodePlaying)
selectableNodes = Nodes[:index]+ Nodes[index+1:]
# We search for the maximum value in any nodes
maxValue = max(selectableNodes, key = lambda node:node.Value).Value
# If the max value is 0, there are no connections
if maxValue == 0:
# We get a random node
nodeRandom = random.choice(selectableNodes)
print("First random Node : ", nodeRandom)
# We make the connection between the randomly selected node and the one with the lowest timing and set their values to 1
G.add_edge(nodePlaying.ID, nodeRandom.ID)
nodePlaying.Value = 1
nodeRandom.Value = 1
else:
# We make a list of nodes that have the maximum value
listMaxNodes = []
for n in selectableNodes:
if n.Value == maxValue:
listMaxNodes.append(n)
# We select a random node between them
nodeToConnect = random.choice(listMaxNodes)
# If the nodes are not already connected, we connect them and increase their values
if G.has_edge(nodePlaying.ID,nodeToConnect.ID) == False :
G.add_edge(nodePlaying.ID, nodeToConnect.ID)
nodeToConnect.Value+=1
nodePlaying.Value+=1
nx.draw_networkx(G,node_color=range(100))
simple_game_without_interference()
We can see that in every simulations, there is always one node in the
center with all the other nodes connected to it. It is always either be
the node with the lowest timing or the first randomnlly choosed Node.
It is like that because, when the second Node is playing, they are the
only two other nodes with a value of 1 instead of 0. The second Node
will randomnly choose one of the two, increasing its value. Then this
node will always be selected and increased at each step. This strategy
take the most powerful node and incraese its value at every rounds.
In
this part, we will play the same game, but when they search for the
best node, their are interferences that change the value of the analyzed
node.
This time we create a 100 nodes.
When searching for the maximum node we search for a maximum. During ths
search, the value of the analyzed node is multiplied by a random number
between two values.
def simple_game_with_interference(ax, interference, iteration):
G = nx.Graph()
Nodes = []
n = 100
# We create n nodes, each one has an id, a value initialized to 0 and a random timing value
# Then we add them to the graph
for i in range(n):
#node = Node(i, 0, random.random(), -1, 1)
node = Node(i, 0, i/100, -1, 0,0)
Nodes.append(node)
G.add_node(i)
# We sort the nodes by the timing value to determine the order in which the nodes will play
Nodes = sorted(Nodes, key=lambda x: x.Timing)
first = "First Node : " + str(Nodes[0].ID)
# For each node
for nodePlaying in Nodes:
# We take the node by timing order
# We make a list of nodes to which the playing node can connect (every node except him)
index = Nodes.index(nodePlaying)
selectableNodes = Nodes[:index]+ Nodes[index+1:]
# We search for the maximum value in any nodes
maxValue = max(selectableNodes, key = lambda node:node.Value).Value
# If the max value is 0, there are no connections
if maxValue == 0:
# We get a random node
nodeRandom = random.choice(selectableNodes)
# We make the connection between the randomly selected node and the one with the lowest timing and set their values to 1
G.add_edge(nodePlaying.ID, nodeRandom.ID)
nodePlaying.NodeConnected = nodeRandom.ID
nodePlaying.Value = 1
nodeRandom.Value = 1
else:
#Searching for the Node with the maximum vizible value
nodeToConnect = None
maxValue = 0
for n in selectableNodes:
#Wwhen looking for the value, modifying it with the interferences
interferedValue = n.Value*random.randint(100-interference,100+interference*10000)/100
if interferedValue > maxValue:
maxValue = interferedValue
nodeToConnect = n
nodePlaying.NodeConnected = nodeToConnect.ID
# If the nodes are not already connected, we connect them and increase their values
if G.has_edge(nodePlaying.ID,nodeToConnect.ID) == False :
G.add_edge(nodePlaying.ID, nodeToConnect.ID)
nodeToConnect.Value+=1
nodePlaying.Value+=1
# Search for the maximum value node to color him differently
maxNode = None
maxValue = 0
for n in Nodes:
if n.Value>maxValue:
maxNode = n
maxValue = n.Value
colorMap = []
color = 17
for n in Nodes:
if n.ID == maxNode.ID:
colorMap.append('#48EB00')
else :
if iteration%2 == 0:
colorMap.append('#76519E')
else :
colorMap.append('#EB110C')
nx.draw_networkx(G, node_color=colorMap, ax=ax, node_size=150, with_labels = False)
ax.axis('off')
return G, Nodes
We then make multiples simulation to have different results.
fig, axs = plt.subplots(3,3,figsize=(20,20))
fig.suptitle("9 random generations of one round\nThe Green point is the node with the maximum value", fontsize=25)
for i in range(9):
simple_game_with_interference(axs[i//3, i%3], 80, i)
Some of these graph are really intresting.
As we can see, most of these graph are articulated around 2 main nodes.
These 2 nodes are the ones that connect in the beggining and have the
highest value. Thanks to the interferences, a playing node can see the
lowest of the two as bigger and connect to it. These two nodes will see
their values increase in parallele and be both attractive for the other
nodes, until one of the two outgrow the other and become more attractive
for the other nodes, even with the interferences, and get a lot more
connections.
In this part, we create a function that play an other round with the same graph and nodes.
In the same order than before, each node will play.
When it plays, a node will look for the node with the biggest value. If
this value is bigger than te current node it is already connected to,it
disconnect and try to connect to the new one. But it will not succeed
to reconnect every time. Each node has a karma value that is equal to
the number of time it disconnected divided by the number of time it
played.
def find_node(Nodes, ID):
for n in Nodes:
if n.ID == ID:
return n
return Node(-1, -100, i/100, -1, 0,0)
def next_round(ax, interference, G, Nodes, iteration):
# For each node
for nodePlaying in Nodes:
# We take the node by timing order
# We make a list of nodes to which the playing node can connect (every node except him)
index = Nodes.index(nodePlaying)
selectableNodes = Nodes[:index]+ Nodes[index+1:]
nodePlaying.Karma_tot +=1
#Searching for the Node with the maximum vizible value
nodeToConnect = Node(i, 0, i/100, -100, 0,0)
maxValue = 0
for n in selectableNodes:
#Wwhen looking for the value, modifying it with the interferences
interferedValue = n.Value*random.randint(100-interference,100+interference*1000)/100
if interferedValue > maxValue:
maxValue = interferedValue
nodeToConnect = n
# Finding the node which we are already connected to
node_already_connected = find_node(Nodes, nodePlaying.NodeConnected)
# If another node as a greater value
if node_already_connected.Value < nodeToConnect.Value:
# We disconnect it from the node its already connected to
if G.has_edge(nodePlaying.ID, node_already_connected.ID):
G.remove_edge(nodePlaying.ID, node_already_connected.ID)
nodePlaying.Value -= 1
# Then we increase its karma
# Having a greater karma is actually bad
nodePlaying.Karma_defect +=1
# We compare the karma to a random number, if it's lower, the node can reconnect
rand = random.random()
if nodePlaying.Karma_defect/nodePlaying.Karma_tot < rand:
# We connect the two nodes and increase their values
G.add_edge(nodePlaying.ID, nodeToConnect.ID)
nodePlaying.NodeConnected = nodeToConnect.ID
nodeToConnect.Value+=1
nodePlaying.Value+=1
else :
nodePlaying.NodeConnected = -1
nodePlaying.Value=0
# We search and color the nodes
maxNode = None
maxValue = 0
for n in Nodes:
if n.Value>maxValue:
maxNode = n
maxValue = n.Value
colorMap = []
color = 0
for n in Nodes:
if n.ID == maxNode.ID:
colorMap.append(200)
else :
colorMap.append(color)
color +=1
nx.draw_networkx(G, node_color=colorMap, ax=ax, node_size=150, with_labels = False)
largest = len(sorted(nx.connected_components(G), key=len, reverse=True)[0])
ax.set_title("Iteration number : " + str(iteration) +"\nSize of the largest connected\ncomponent :" + str(largest), fontsize=15)
ax.axis('off')
return G, Nodes
We play a first round as usual, then 8 other round where the node can disconnect.
fig, axs = plt.subplots(3,3,figsize=(20,20))
interference=99
G, Nodes = simple_game_with_interference(axs[0,0],80, 1)
fig.suptitle("A first generation, then 8 rounds of the game\nThe Yellow point is the node with the maximum value", fontsize=25)
for i in range(1,9):
G, Nodes = next_round(axs[i//3,i%3],interference, G, Nodes, i)
As we can see in the graph, in the first round, two nodes where bigger than the other.
In the first iteration, some nodes where not connected to one of the two
pricipal nodes, and saw the orther one as bigger. So the disconnected.
They had 1/1 chance of not being connected and are left alone.
In the second round, some nodes tryed and succeed to connect to the
other principal node. Other werre disconnected and left alone. And some
of the alone nodes reconnected to the biggest node.
With more and more rounds, more and more nodes switched to the biggest
node and, as they disconnected less comparing to the number of time they
played.
In the end all the nodes are connected to the biggest node.